package test.ali;

/**
 * @Description 课程表
 * @Author Firenut
 * @Date 2023-09-16 11:53
 */


import java.util.*;

/**
     “algorithms” : ["data structures"],
     “calculs”: ["linear algebra],
     "compeliers":["data structures",“formal languages”,“computer organization”],
     “data structures”:[“mathmatics"] }
     以上的map中的元组key是一门学科名，value是学科列表，表示key这门学科依赖列表里的所有value
     需要先学value列表里的学科后，才能学key这门学科
     请打印出一种要学习所有学科的先后顺序列表


 */
public class kcb {
    public static void main(String[] args) {
        HashMap<String, List<String>> map = new HashMap<>();
        map.put("algorithms", Arrays.asList("data structures"));
        map.put("calculs", Arrays.asList("linear algebra"));
        map.put("compeliers", Arrays.asList("data structures","formal languages","computer organization"));
        map.put("data structures", Arrays.asList("mathmatics"));
        System.out.println(getCourseOrder(map));
    }

    static List<String> getCourseOrder(Map<String, List<String>> map) {
        // 每个结点的度数
        Map<String, Integer> du = new HashMap<>();
        // 课程映射，key是先行课程，value是后置课程
        Map<String, List<String>> grip = new HashMap<>();

        for (Map.Entry<String, List<String>> entry : map.entrySet()) {
            String course = entry.getKey();
            List<String> preList = entry.getValue();

            if (!grip.containsKey(course)) {
                grip.put(course, new ArrayList<>());
            }

            // 记录度数及依赖关系
            for (String pre : preList) {
                // value列表对应的度数是0（如果存在相当于是覆盖，value值不变，不存在才是0，这样就不会覆盖错了）
                du.put(pre, 0);
                // 每个先行课程对应的后置课程(方便后续更新度数)
                if (!grip.containsKey(pre)) {
                    grip.put(pre, new ArrayList<>());
                }
                grip.get(pre).add(course);
            }

            // 每个key对应的度数是value的个数
            du.put(course, preList.size());
        }

        LinkedList<String> queue = new LinkedList<>();
        for (Map.Entry<String, Integer> m : du.entrySet()) {
            if (m.getValue() == 0) {
                queue.addLast(m.getKey());
            }
        }

        List<String> ans = new ArrayList<>();
        while (!queue.isEmpty()) {
            String first = queue.removeFirst();
            ans.add(first);
            // 更新度数(该课程所指向的其他课程)
            for (String c : grip.get(first)) {
                du.put(c, du.get(c) - 1);
                if (du.get(c) == 0) {
                    queue.addLast(c);
                }
            }
        }
        return ans;
    }
}

